In the field of computer graphics, texture mapping is a known technique used to create the appearance of complexity on the surface of rendered objects without actually having to model every detail of the object's surface. Typically, the technique involves mapping a two-dimensional function or array (the texture) onto an object in three-dimensional object space and then projecting the resultant image back to two-dimensional screen space for display. For purposes of this discussion, texture space will be denoted (s,t) and screen space will be denoted (x,y).
The phrase "texture map" refers to the function or array that is used in the texture mapping process. A common two-dimensional texture map might consist of a repeatable pattern for representing a material, such as wood or marble for example. Such a texture map is made up of a plurality of numerical values called "texels." Each texel in the texture map has its own unique s,t coordinates within the texture map array. A texel's numerical value usually corresponds to an RGB color value and perhaps also to an alpha value. Often, the correspondence between numerical texel values and RGB/alpha values is determined with a look-up table. On the other hand, the RGB/alpha values may also be independent bit fields in a multi-bit texel value. For example, in a system that uses 32-bits for each texel value, 8 bits each may be allocated in each texel value for the R, G, B and alpha components. But in systems that use only 8 bits for each texel value, it may be preferable to use the 8 bits as an index to a look-up table where the R, G, B and alpha values are stored. The texture maps themselves are usually stored either in frame buffer memory or in system memory, or both.
The s and t coordinates for each texel in an actual texture map are whole numbers. Likewise, the x and y coordinates for each physical pixel in screen space are whole numbers. But the abstract process of mapping the x,y coordinates for a given pixel to the s,t coordinates of a texture map yields target s,t coordinates that each have an integer portion and a fractional portion. This is so because, in general, the mapped s,t coordinates corresponding to a pixel usually will not coincide perfectly with the location of one of the texels in the texture map. Rather, the mapped s,t coordinates for a pixel will usually lie somewhere in a square region defined by four adjacent texels.
For purposes of this discussion, any four adjacent texels that define such a region in a texture map will be referred to as a "texel quad," and the location of the texels defining the texel quad will be referred to as the "corners" of the texel quad. More specifically, the "upper left corner" of a texel quad will refer to the nearest texel in the pertinent texture map whose s coordinate is less than or equal to the s coordinate of the pixel and whose t coordinate is less than or equal to the t coordinate of the pixel. The "upper right corner" of a texel quad will refer to the nearest texel in the pertinent texture map whose s coordinate is less than or equal to the s coordinate of the pixel and whose t coordinate is greater than or equal to the t coordinate of the pixel. The "lower left corner" of a texel quad will refer to the nearest texel in the pertinent texture map whose s coordinate is greater than or equal to the s coordinate of the pixel and whose t coordinate is less than or equal to the t coordinate of the pixel. The "upper right corner" of a texel quad will refer to the nearest texel in the pertinent texture map whose s coordinate is greater than or equal to the s coordinate of the pixel and whose t coordinate is greater than or equal to the t coordinate of the pixel.
By way of further explanation, the phrase "texel address" as used in this discussion will refer not just to the specific address for a particular texel value, but to the address of the multi-bit data word that contains a particular texel value. For example, in a system that uses 8 bits per texel, a 32-bit data word could include four different texel values; thus, the address for a 32-bit data word could correspond to four different texel values.
Once the integer and fractional parts of the s,t coordinates are determined for a given pixel, the texels that make up the texel quad surrounding the mapped s,t coordinates are interpolated to produce a final texel value for the pixel. This process is called "bilinear interpolation." By way of explaining bilinear interpolation, assume an arbitrary texel quad 100 as shown in FIG. 1 whose corner coordinates and texel values are as follows:
TABLE 1 ______________________________________ Texel s Coordinate t Coordinate Texel Value ______________________________________ 102 (T1, upper left) 5 8 20 104 (T2, upper right) 5 9 25 106 (T3, lower left) 6 8 30 108 (T4, lower right) 6 9 35 ______________________________________
Also assume an arbitrary pixel 110 whose x,t coordinates map to the following s,t coordinates: s=5.25, t=6.25. The process of bilinear interpolation goes as follows: First, the values of texels 102 and 104 are linearly interpolated to determine a value for point 112, and the values of texels 106 and 108 are linearly interpolated to determine a value for point 114. Then, the values of points 112 and 114 are linearly interpolated to determine the value for pixel 110. In this example, the value for point 112 would be 21.25, the value for point 114 would be 31.25, and the value for the pixel would be 23.75. Note that only the integer part of the pixel's s,t coordinates are needed to locate which texel quad will be used as a basis for the interpolation, and only the fractional part of the pixel's s,t coordinates are needed to actually perform the interpolation.
From the above example, it can be seen that bilinear interpolation in texture mapping requires four texel values for each pixel. Moreover, in texture mapping systems that utilize a multum in parvo scheme (i.e., "MIP mapping"), trilinear interpolation is often performed, requiring eight texel values for each pixel. Because each texel is stored in a texture map somewhere either in frame buffer memory or system memory, and because of the time required to read from those memories, it is important to access required texel values in an efficient manner.
One possible solution to the memory access efficiency problem is to dedicate a traditional cache memory system to the task. But traditional cache memory systems are expensive to implement--not only because of the cost of high speed RAM, but also because of the overhead associated with the relatively large and complex circuitry and algorithms required to control traditional cache systems. In short, a traditional cache memory solution cannot easily be cost justified for solving such a special-case problem in such a special-purpose computer subsystem.
Therefore, a need exists for a relatively inexpensive memory arrangement that will improve read efficiency in the context of performing bilinear interpolation during texture mapping.